package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.ListNode;

public class code142_环形列表2 {

    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(
                new int[]{
                        1,2,3,4,5
                }
        );
        listNode.next.next.next.next.next = listNode.next.next;
        System.out.println(new code142_环形列表2().detectCycle(listNode));
    }

    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode one = head;
        ListNode two = head;
        int index = 0;
        while (true) {
            one = one.next;
            if (two.next != null) {
                two = two.next.next;
            } else {
                two = null;
            }
            index++;
            if (one == null || two == null) {
                return null;
            }
            if (one == two) {
                break;
            }
        }
        int start = 0;
        one = head;
        two = head;
        while (true) {
            if(start == index){
                one = one.next;
                two= two.next;
                if(one == two){
                    return one;
                }
            }else{
                one = one.next;
                start++;
            }
        }
    }

    /**
     * 更好的思路,其实在二进的时候如果相遇了就表示这个位置的是之前到之后的中点
     * 通过图可以发现一个规律,相遇点到之后的距离就是初始点到入环点的距离
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {//说明有环
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}
